package ch3stacks;

import java.util.Arrays;
import java.util.Stack;

class StackSort {
	Stack<Integer> s1 = new Stack<>();
	Stack<Integer> s2 = new Stack<>();

	void sort() {
		while (!s1.empty()) {
			Integer pop = s1.pop();
			Integer peek = s2.isEmpty() ? null : s2.peek();
			if (peek == null || pop < peek) {
				s2.push(pop);
				continue;
			}

			int count = 0;
			while (!s2.isEmpty() && pop > peek) {
				s1.push(s2.pop());
				count++;
				peek = s2.isEmpty() ? null : s2.peek();
			}

			s2.push(pop);

			for (int i = 0; i < count; i++) {
				s2.push(s1.pop());
			}
		}

		for (Integer i : s2) {
			System.out.print(i + " ");
		}
	}
}

public class Ex6 {

	public static Stack<Integer> sort(Stack<Integer> s) {
		Stack<Integer> r = new Stack<Integer>();
		while (!s.isEmpty()) {
			int tmp = s.pop();
			while (!r.isEmpty() && r.peek() < tmp) {
				s.push(r.pop());
			}
			r.push(tmp);
		}
		return r;
	}

	public static void main(String... argv) {
		StackSort stackSort = new StackSort();

		stackSort.s1.addAll(Arrays.asList(new Integer[] { 3, 4, 1, 2 }));

//		stackSort.sort();

		Stack<Integer> sort = sort(stackSort.s1);
		int a=1;
	}
}
